package com.lw.leetcode.tree.b;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * 6139. 受限条件下可到达节点的数目
 *
 * @author liw
 * @version 1.0
 * @date 2022/8/7 21:16
 */
public class ReachableNodes {

    private Map<Integer, List<Integer>> map;
    private int count = 0;
    private int[] arr;

    public int reachableNodes(int n, int[][] edges, int[] restricted) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int[] edge : edges) {
            map.computeIfAbsent(edge[0], v -> new ArrayList<>()).add(edge[1]);
            map.computeIfAbsent(edge[1], v -> new ArrayList<>()).add(edge[0]);
        }
        if (map.get(0) == null) {
            return 0;
        }

        int[] arr = new int[n];
        for (int i : restricted) {
            arr[i] = 1;
        }
        this.map = map;
        this.arr = arr;
        arr[0] = 1;
        count++;
        find(0);
        return count;
    }

    private void find(int index) {
        for (int v : map.get(index)) {
            if (arr[v] == 1) {
                continue;
            }
            count++;
            arr[v] = 1;
            find(v);
        }
    }

}
